package com.wfm.leetcode.editor.cn;
public class POne62寻找峰值{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 从随机一个i，优化成二分搜索i
    // i-1<i>i+1 峰值就是i
    // 如果i>i+1 下坡：肯定在左边，i要往左移
    // 如果i<i+1 上坡：肯定在右边，i要往右移
    // 如果i-1>i<i+1,谷底，随意但是我们规定往右
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int l=0,r=n-1,ans=-1;
        while (l<=r){
            int m = (l+r)/2;
            if(compare(nums,m-1,m)<0&&compare(nums,m,m+1)>0){
                ans=m;
                return ans;
            }
            else if(compare(nums,m,m+1)<0){
                l=m+1;
            }else{
                r=m-1;
            }
        }
        return ans;
    }

    // 需要考虑-1 和n的边界问题。如果一个是边界一个不是，直接非边界的大
    // 都是边界，则相等
    // 否则都不是边界的话，正常比较
    private int compare(int[] nums, int idx1, int idx2) {
        int[] nums1 = get(nums,idx1);
        int[] nums2 = get(nums,idx2);
        if(nums1[0]!=nums2[0]){
            return nums1[0]>nums2[0]?1:-1;
        }
        if(nums1[1]==nums2[1]){
            return 0;
        }
        return nums1[1]>nums2[1]?1:-1;
    }

    private int[] get(int[] nums, int idx) {
        if(idx==-1||idx==nums.length){
            return new int[]{0,0};
        }
        return new int[]{1,nums[idx]};
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new POne62寻找峰值().new Solution();
    }
}